/**
 * @file 72.EditDistance.cc
 * @author snow-tyan (zziywang@163.com)
 * @brief {Life is too short to learn cpp.}
 * @version 0.1
 * @date 2021-11-19
 * 
 * @copyright Copyright (c) 2021
 * 
 * LCS + 编辑距离
 * 718.最长重复子数组 -- 连续
 * 1143.最长公共子序列 -- 不连续 == 1035.不相交的线 * 
 * 392.判断子序列 -- 这才是最难的 双指针/dp
 * 583.两个字符串的删除操作 
 * 72.编辑距离 
 * 115.不同的子序列
 */

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

template <typename T>
void print(const T &Containers)
{
    typename T::const_iterator it = Containers.begin();
    while (it != Containers.end()) {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}

class Solution
{
public:
    // 718. 最长公共子数组的长度
    int findLength(vector<int> &nums1, vector<int> &nums2)
    {
        // dp[i][j] 以nums1[i]结尾，nums2[j]结尾的公共最长子数组长度
        // 当nums1[i]==nums2[j]时dp[i][j]=dp[i-1][j-1]+1
        int m = nums1.size(), n = nums2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        int maxDp = 0;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                maxDp = max(maxDp, dp[i][j]);
            }
        }
        return maxDp;
    }
    // 1143. 最长公共子序列
    int longestCommonSubsequence(string text1, string text2)
    {
        // dp[i][j] 以t1[i]结尾，t2[j]结尾的公共最长子序列长度
        // 如果t1[i]==t2[j]，那么dp[i][j]=dp[i-1][j-1]+1
        // 否则取max(dp[i-1][j],dp[i][j-1])
        int m = text1.length(), n = text2.length();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        int maxDp = 0;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (text1[i - 1] == text2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
                maxDp = max(maxDp, dp[i][j]);
            }
        }
        return maxDp;
    }
    // 1035.不相交的线
    int maxUncrossedLines(const vector<int> &nums1, const vector<int> &nums2)
    {
        int m = nums1.size(), n = nums2.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        int maxDp = 0;
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
                maxDp = max(maxDp, dp[i][j]);
            }
        }
        return maxDp;
    }
    // 392. 判断s是否为t的子序列
    bool isSubsequence(string s, string t)
    {
        // 通常想法：双指针
#if 0
        int m = s.length(), n = t.length();
        int i = 0, j = 0;
        while (i < m && j < n) {
            if (s[i] == t[j]) {
                ++i, ++j;
            } else {
                ++j;
            }
        }
        return i == m;
#endif
        // 编辑距离，删除 []闭区间
        // dp[i][j] s[0:i-1]和t[0:j-1]相同子序列的长度
        // -- 编辑距离是s->t,这里是t->s，插入和删除自然反过来
        // dp[i][j-1] 删除
        // dp[i-1][j] 插入
        // dp[i-1][j-1] 替换
        int m = s.length(), n = t.length();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (s[i - 1] == t[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = dp[i][j - 1];
                }
            }
        }
        return dp[m][n] == m;

        // 进阶：如果大量S来匹配T，怎么办？
        // 把T做成一个表，m行26列，记录每个字符第一次出现的位置
        // dp[i][j] 到T的第i个位置为止，其后j个字符出现的第一个位置
        // dp[i][j] = i (T[i]==j) dp[i][j] = dp[i+1][j]
        // 详细代码见python
    }
    // 583.
    int minDistance583(string word1, string word2)
    {
        // word1 word2 通过删除变成某个公共子串
        // 等价于 word1 通过删除+插入 -> word2
        int m = word1.length(), n = word2.length();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        // 边界
        for (int i = 1; i <= m; ++i) {
            dp[i][0] = i;
        }
        for (int j = 1; j <= n; ++j) {
            dp[0][j] = j;
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (word1[i - 1] == word2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;
                }
            }
        }
        return dp[m][n];
    }
    // 72.
    int minDistance72(string word1, string word2)
    {
        int m = word1.length(), n = word2.length();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        // 边界
        for (int i = 1; i <= m; ++i) {
            dp[i][0] = i;
        }
        for (int j = 1; j <= n; ++j) {
            dp[0][j] = j;
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (word1[i - 1] == word2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = min(min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                }
            }
        }
        return dp[m][n];
    }
    // 115.
    int numDistinct(string s, string t)
    {
        // dp[i][j] s[0:i-1]中出现t[0:j-1]子序列的个数
        using ll = long long;
        int m = s.length(), n = t.length();
        if (m < n) {
            return 0;
        }
        vector<vector<ll>> dp(m + 1, vector<ll>(n + 1, 0));
        // 边界
        for (int i = 0; i <= m; ++i) {
            dp[i][0] = 1; // t空串，算一个子序列
        }
        // s空串就直接等于0了
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (s[i - 1] == t[j - 1]) {
                    // 相等时 s[i - 1]可以选择匹配或者不匹配，这是难点
                    // dp[i-1][j-1] s[i-1]选择匹配 s[0:i-2]和t[0:j-2]匹配数量
                    // dp[i-1][j] s[i-1]选择不匹配 s[0:i-2]和t[0:j-1]匹配数量
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
                } else {
                    // 不相等时只能不匹配
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[m][n];
    }
};

void test718()
{
    vector<int> nums1 = {1, 2, 3, 2, 1};
    vector<int> nums2 = {3, 2, 1, 4, 7};
    cout << Solution().findLength(nums1, nums2) << endl;
}
void test1143()
{
    string t1 = "abcde";
    string t2 = "ace";
    cout << Solution().longestCommonSubsequence(t1, t2) << endl;       // 3
    cout << Solution().longestCommonSubsequence("abc", "abc") << endl; // 3
    cout << Solution().longestCommonSubsequence("abc", "def") << endl; // 0
}
void test1035()
{
    vector<int> nums1 = {2, 5, 1, 2, 5};
    vector<int> nums2 = {10, 5, 2, 1, 5, 2};
    cout << Solution().maxUncrossedLines(nums1, nums2) << endl;
    cout << Solution().maxUncrossedLines({1, 3, 7, 1, 7, 5}, {1, 9, 2, 5, 1}) << endl;
}
void test392()
{
    std::cout << Solution().isSubsequence("abc", "ahbgdc") << std::endl; // true
    std::cout << Solution().isSubsequence("axc", "ahbgdc") << std::endl; // false
}
void test583()
{
    std::cout << Solution().minDistance583("sea", "eat") << std::endl;       //2
    std::cout << Solution().minDistance583("leetcode", "etco") << std::endl; //4
}
void test72()
{
    std::cout << Solution().minDistance72("horse", "ros") << std::endl;           //3
    std::cout << Solution().minDistance72("intention", "execution") << std::endl; //5
}
void test115()
{
    std::cout << Solution().numDistinct("rabbbit", "rabbit") << std::endl; // 3
    std::cout << Solution().numDistinct("babgbag", "bag") << std::endl;    // 5
}

int main()
{
    // test718();
    // test1143();
    // test1035();
    // test392();
    // test583();
    // test72();
    test115();
    return 0;
}